﻿using System;
using System.Collections.Generic;

namespace Bettzueche.Datenstrukturen
{
    /// <summary>
    /// Eine Priority Queue: nach Priorität sortierte Liste.
    /// </summary>
    /// <typeparam name="T">Typ der Elemente, implementiert <see cref="System.IComparable{T}"/>.</typeparam>
    /// <remarks>
    /// Basiert auf der Implementierung von James McCaffrey, 11/02/2012:
    /// http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx (zuletzt besucht am 28.06.2014)
    /// <para>
    /// Eine priority queue hält Elemente mit einer Art von Priorität, die durch die Methode <c>CompareTo</c> des Interface
    /// <see cref="System.IComparable{T}"/> wiedergegeben wird. Das generiche Element muss dieses Interface implementieren.
    /// Es wird immer das Element mit der höchsten Priorität entfernt. Priority Queues werden in vielen Algorithmen gebraucht,
    /// insbesondere bei graphenbasierten Algorithmen zur Suche des kürzesten Pfades.
    /// </para><para>
    /// Die Implementierung dieser Priority Queue basiert intern auf einem Binary Heap. Die Komplexität von 
    /// <list type=">">
    /// <item><c>Enqueue</c> ist O(lg n)</item>
    /// <item><c>Dequeue</c> ist O(lg n)</item>
    /// </list></para>
    /// </remarks>
    public class PriorityQueue<T> : IEnumerable<T>
    {
        private List<T> _data;
        IComparer<T> _comparer;


        /// <summary>
        /// Gets the number of elements contained in the <see cref="Bettzueche.Datenstrukturen.PriorityQueue{T}"/>.
        /// </summary>
        /// <value>
        /// The count.
        /// </value>
        public int Count {
            get { return _data.Count; }
        }

        /// <summary>
        /// Initializes a new empty instance of the <see cref="PriorityQueue{T}" /> class.
        /// </summary>
        /// <param name="comparer">The comparer. (see <see cref="System.Collections.Generic.IComparer{T}" />)</param>
        /// <exception cref="System.ArgumentNullException">comparer</exception>
        public PriorityQueue(IComparer<T> comparer) {
            if (comparer == null)
                throw new ArgumentNullException("comparer");
            this._data = new List<T>();
            _comparer = comparer;
        }



        /// <summary>
        /// Enqueues the specified item.
        /// </summary>
        /// <param name="item">The item, not null</param>
        public void Enqueue(T item) {
            _data.Add(item);
            int childIdx = _data.Count - 1; // child index; start at end
            while (childIdx > 0) {
                int parentIdx = (childIdx - 1) / 2; // parent index
                // fertig, wenn Kind größer-gleich Vater
                if (_comparer.Compare(_data[childIdx], _data[parentIdx]) >= 0)
                    break;
                T tmp = _data[childIdx];
                _data[childIdx] = _data[parentIdx];
                _data[parentIdx] = tmp;
                childIdx = parentIdx;
            }
        }

        /// <summary>
        /// Dequeues this instance.
        /// </summary>
        /// <returns></returns>
        /// <exception cref="System.IndexOutOfRangeException">
        /// if this Queue is empty.
        /// </exception>
        public T Dequeue() {
            // assumes pq is not empty; up to calling code
            int last = _data.Count - 1; // last index (before removal)
            T frontItem = _data[0];   // fetch the front
            _data[0] = _data[last];
            _data.RemoveAt(last);

            --last; // last index (after removal)
            int parntIdx = 0; // parent index. start at front of pq
            while (true) {
                int childIdx = parntIdx * 2 + 1; // left child index of parent
                if (childIdx > last)
                    break;  // no children so done
                int rc = childIdx + 1;     // right child
                if (rc <= last && _comparer.Compare(_data[rc], _data[childIdx]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
                    childIdx = rc;
                if (_comparer.Compare(_data[parntIdx], _data[childIdx]) <= 0)
                    break; // parent is smaller than (or equal to) smallest child so done
                T tmp = _data[parntIdx];
                _data[parntIdx] = _data[childIdx];
                _data[childIdx] = tmp; // swap parent and child
                parntIdx = childIdx;
            }
            return frontItem;
        }

        /// <summary>
        /// Gibt das erste Element, ohne es zu entfernen.
        /// </summary>
        /// <returns>Das erste Element</returns>
        /// <remarks>
        /// Achtung: Bei Referenztypen kann eine Änderung von Objekteigenshcaften zur Inkonsistenz dieser Priority Queue führen!
        /// </remarks>
        public T Peek() {
            T frontItem = _data[0];
            return frontItem;
        }


        /// <summary>
        /// Returns a <see cref="System.String" /> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="System.String" /> that represents this instance.
        /// </returns>
        public override string ToString() {
            string s = this.GetType().FullName;
            s += " (Count=" + this.Count +")";
            return s;
        }

        /// <summary>
        /// Determines whether this instance is consistent.
        /// </summary>
        /// <returns></returns>
        public bool IsConsistent() {
            // is the heap property true for all data?
            if (_data.Count == 0)
                return true;
            int li = _data.Count - 1; // last index
            for (int pi = 0; pi < _data.Count; ++pi) { // each parent index
                int lci = 2 * pi + 1; // left child index
                int rci = 2 * pi + 2; // right child index

                if (lci <= li && _comparer.Compare(_data[pi], _data[lci]) > 0)
                    return false; // if lc exists and it's greater than parent then bad.
                if (rci <= li && _comparer.Compare(_data[pi], _data[rci]) > 0)
                    return false; // check the right child too.
            }
            return true; // passed all checks
        } // IsConsistent


        /// <summary>
        /// Returns an enumerator that iterates through the collection in priority order.
        /// Komplexität = O(n²)!
        /// </summary>
        /// <returns>
        /// A <see cref="T:System.Collections.Generic.IEnumerator`1" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator() {
            var copy = new PriorityQueue<T>(this._comparer);
            copy._data = new List<T>(this._data);
            if (copy.Count == 0)
                yield break;
            yield return copy.Dequeue();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return this.GetEnumerator();
        }
    }
}
